Data from both individuals and businesses is increasingly collected, aggregated and analysed to provide new services. There is a corresponding desire to enable both storage and processing of such data in a secure and privacy-preserving way, in line with the increasing public concerns and strict regulatory requirements for the protection of such data. Secure Multi-Party Computation (MPC) is a mechanism by which a number of parties can collaborate to compute an agreed function of their inputs, ensuring both confidentiality of the data and the integrity of the resulting output. Private computations over distributed data are applicable in many scenarios, allowing multiple organizations to jointly utilize their private or business confidential data to provide a service (e.g., Internet Service Providers troubleshooting network outages), and enabling processing of personal data stored on individuals' mobile devices.
MPC may be based on secret sharing or garbled circuits. In secret sharing, each peer distributes shares that are cryptographically constructed from confidential data (i.e., the secrets), such that only a pre-determined subset of parties can reconstruct the secrets.
Some secret sharing schemes are threshold-based, requiring access to a minimum of t shares to recover the secret, where t is a predetermined threshold. Shamir secret sharing is a threshold scheme that provides perfect secrecy, i.e., no information is leaked by any subset of fewer than t shares. However, the size of each share is at least the size of the secret. Consequently, the use of secret sharing in services that rely on large amounts of data can be severely limited.
This has motivated the study of ramp secret sharing schemes, which allow a controlled leakage of information about the secret when the number of available shares is below t but above a second threshold t−L. The benefit of the relaxed security guarantee is a lower share size, reduced by a factor of L compared to Shamir or other threshold schemes with perfect secrecy. Strong ramp schemes increase the security of generic ramp schemes, by placing the same condition on leakage of any part of the secret, while maintaining the reduced communication overhead.
Despite the promise of strong ramp schemes, there is limited prior work on construction methods for such schemes.
Any discussion of documents, acts, materials, devices, articles or the like which has been included in the present specification is not to be taken as an admission that any or all of these matters form part of the prior art base or were common general knowledge in the field relevant to the present disclosure as it existed before the priority date of each claim of this application.
Throughout this specification the word “comprise”, or variations such as “comprises” or “comprising”, will be understood to imply the inclusion of a stated element, integer or step, or group of elements, integers or steps, but not the exclusion of any other element, integer or step, or group of elements, integers or steps.